package s12_经典算法.a0_回溯算法;

import java.util.Arrays;

/**
 * <code>{@link MiGong}</code>
 * <p>
 * description: MiGong
 * <p>
 *
 * @author 西瓜瓜 on 2022/2/13 17:58
 */
public class MiGong {

    public static void main(String[] args) {
        // 创建一个 8行 7列的迷宫
        int[][] map = new int[8][7];
        // 初始化设置地图
        initMap(map);

        setWay(map, 1, 1);


        sout(map);

    }

    /**
     * 约定：当map[i][j] == 0，表示还没走过，==1 表示墙壁， ==2表示通路可以走 ==3 表示该位置已经走过但是走不通
     * 行进方向：下 右 上 左，如果该点走不通，就回溯
     * @param map 表示地图
     * @param i 表示从哪个位置开始找
     * @param j 表示从哪个位置开始找
     * @return 找到通路就返回true，否则返回false
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if(map[6][5] == 2) {
            // 说明通路已经找到
            return true;
        }

        if(map[i][j] == 0) {
            // 如果当前点没有走过
            // 假定改点是可以走通的
            map[i][j] = 2;
            if(setWay(map, i+1, j)) {
                // 向下走能走通
                return true;
            } else if(setWay(map, i, j+1)) {
                // 向右走能走通
                return true;
            } else if(setWay(map, i-1, j)) {
                // 向上走能走通
                return true;
            } else if(setWay(map, i, j-1)) {
                // 向左走能走通
                return true;
            } else {
                // 都走不通
                map[i][j] = 3;
                return false;
            }
        } else {
            // 如果map[i][j] != 0, 可能是1,2,3
            return false;
        }

    }

    private static void initMap(int[][] map) {
        // 1表示墙壁
        // 将迷宫上下置为墙壁
        for(int i=0; i<7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        // 将迷宫左右置为墙壁
        for(int i=0; i<8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        // 将[3][1]、[3][2]设为挡板
        map[3][1] = 1;
        map[3][2] = 1;
        map[2][2] = 1;
    }

    private static void sout(int[][] map) {
        for (int[] ints : map) {
            System.out.println(Arrays.toString(ints));
        }
    }
}
